//
//  main.swift
//  704-二分查找
//
//  Created by lhc on 2023/10/5.
//

import Foundation

class Solution {
    
    static func search<E: Comparable>(arr: [E], target: E) -> Int {
        var left = 0
        var right = arr.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if arr[mid] == target {
                return mid
            }else if arr[mid] < target {
                left = mid + 1
            }else if arr[mid] > target {
                right = mid - 1
            }
        }
        
        return -1
    }
    
    static func searchByRecursion<E: Comparable>(arr: [E], target: E) -> Int {
        return recursion(arr: arr, target: target, left: 0, right: arr.count - 1)
    }
    
    static private func recursion<E: Comparable>(arr: [E], target: E, left: Int, right: Int) -> Int {
        if left > right {
            return -1
        }
        
        let mid = left + (right - left) / 2
        if arr[mid] == target {
            return mid
        }else if arr[mid] < target {
            return Solution.recursion(arr: arr, target: target, left: mid + 1, right: right)
        }else {
            return Solution.recursion(arr: arr, target: target, left: left, right: mid - 1)
        }
        
    }
}

func test<E: Comparable>(arr: [E], fun: ([E], E) -> Int, target: E) {
    
    let result = fun(arr, target)
    if result != -1 {
        print("\(arr)第\(result)位 = \(target)")
    }else {
        print("\(arr)中没有\(target)")
    }
}

let n = [-1, 0, 3, 5, 9, 12]
test(arr: n, fun: Solution.search, target: 9)
test(arr: n, fun: Solution.search, target: 10)
test(arr: n, fun: Solution.searchByRecursion, target: 9)
test(arr: n, fun: Solution.searchByRecursion, target: 10)

